// https://leetcode.cn/problems/find-k-closest-elements/
// Created by ade on 2022/8/25.
// 给定一个 排序好 的数组 arr ，两个整数 k 和 x ，
// 从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

// lower_bound 找到第一个大于等于x 的位置
// upper_bound 找到第一个大于x 的位置
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
    // 排序法
    vector<int> findClosestElements1(vector<int> &arr, int k, int x) {
        sort(arr.begin(), arr.end(), [&](const int &a, const int &b) {
            return abs(a - x) < abs(b - x) || abs(a - x) == abs(b - x) && a < b;
        });
        sort(arr.begin(), arr.begin() + k);
        return {arr.begin(), arr.begin() + k};
    }

    // 二分法
    vector<int> findClosestElements(vector<int> &arr, int k, int x) {
        int r = lower_bound(arr.begin(), arr.end(), x) - arr.begin();
        int l = r - 1;
        while (k--) {
            if (l < 0) {
                r++;
            } else if (r >= arr.size()) {
                l--;
            } else if (x - arr[l] <= arr[r] - x) {
                l--;
            } else {
                r++;
            }
        }
        return {arr.begin() + l + 1, arr.begin() + r};
    }
};

int main() {
    Solution so;
    vector<int> nums = {0, 2, 2, 4, 6, 7, 8, 9, 9};
//    cout << "lower:" << endl;
//    cout << *lower_bound(nums.begin(), nums.end(), 2) << endl;
//    cout << lower_bound(nums.begin(), nums.end(), 2) - nums.begin() << endl;
//    cout << "upper:" << endl;
//    cout << *upper_bound(nums.begin(), nums.end(), 4) << endl;
//    cout << upper_bound(nums.begin(), nums.end(), 4) - nums.begin() << endl;
    auto res = so.findClosestElements(nums, 4, 6);
    for (auto i : res) {
        cout << i << ",";
    }
    cout << endl;
    return 0;
}